package test3;

import java.util.Arrays;
import java.util.Scanner;

public class Solution2 {// 堆排序 - 大根堆
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入需要排序数字的个数：");
        int num = sc.nextInt();
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = sc.nextInt();
        }
        heapSort(arr, num);
        System.out.println(Arrays.toString(arr));
    }
    /**
     * @param arr 需要调整的数组
     * @param i 非叶子节点在数组的索引
     * @param length 表示对多少个数组继续调整，每次调整后减一
     */
    public static void heapify(int[] arr, int length, int i){//维护堆
        if (i >= length){//调整节点超出边界结束递归
            return;
        }
        int leftNode = 2 * i + 1, rightNode = 2 * i + 2;
        int max = i;
        //比较根节点和子节点的大小
        if (leftNode < length && arr[leftNode] > arr[max]){
            max =  leftNode;
        }
        if (rightNode < length && arr[rightNode] > arr[max]){
            max = rightNode;
        }
        if (max != i){//当前节点需要调整
            int temp = arr[i];
            arr[i] = arr[max];
            arr[max] = temp;
            heapify(arr, length, max);
        }
    }

    private static void buildMaxHeap(int[] arr, int length){//创建大根堆
        int lastNode = length - 1;
        int parentNode = (lastNode - 1) / 2;
        for (int i = parentNode; i >= 0; i--){//自底向上维护堆
            heapify(arr, length, i);
        }
    }

    private static void heapSort(int[] arr, int length){
        buildMaxHeap(arr, length);
        for (int i = length - 1; i >= 0; i--){//将最大节点放到末尾，再维护堆
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
}
